1. Field of the Invention
This invention relates generally to communications systems and particularly to wireless mesh networks. Still more particularly this invention relates to a method for quickly and optimally designing a wireless mesh network.
2. Description of the Related Art
Wireless mesh networks (WMNs) are systems of wireless access points (APs) interconnected in a mesh to provide digital services to client devices via radio transmission. These client devices typically are laptop computers, personal digital assistants (PDAs), sensor systems, or other electronic devices requiring network connectivity. WMNs support any type of digital communication, including email, Internet access, file transfer, and voice communication, and they can transmit this information rapidly, reliably, and efficiently.
WMNs can be deployed and configured to fulfill communications requirements, and they have several characteristics that make them particularly well suited to austere environments (i.e., scenarios where communications infrastructure is seriously degraded, destroyed or non-existent). These characteristics include the ability to reroute traffic dynamically when APs are lost or added to the network and the ability to operate with no infrastructure other than a local power source (such as a battery or small generator). Unlike devices connected to wireless local area networks (WLANs) or “hotspots,” clients on WMNs are free to roam from the coverage area of one wireless AP to another without loss of service.
Military and civilian organizations can benefit from the advantages provided by WMNs. The Enhanced Company Operations (ECO) concept of the United States Marine Corps (USMC) relies on separation and coordination of tactical units to gain an advantage over the enemy. This concept requires voice, data, and surveillance fused into a single common operating picture. Tactical units must gravitate from push-to-talk radio systems to mobile ad hoc mesh networking. WMNs can quickly and securely relay time-critical information such as intelligence reports, tactical orders, and location sensor readings to separated small units in support of ECO.
The Department of Homeland Security (DHS) requires that the public safety community have the ability to communicate and share information as authorized when it is needed, where it is needed, and in a mode or form that allows the practitioners to effectively use it. Data communications are becoming increasingly important to public safety practitioners to provide the information needed to carry out their missions. During humanitarian assistance and disaster relief (HA/DR) operations, WMNs can provide maps, floor plans, video surveillance, emergency aid requests, and other critical information to personnel.
The physical topology (i.e., the locations of the wireless APs) of a WMN is critical to its performance. Network engineers must place and configure wireless APs to provide service to clients in desired areas, while meeting restrictions on number, placement, and characteristics of APs, as well as requirements for coverage, bandwidth, and other service standards. Consideration must also be given to the effects of terrain and other aspects of the operating environment on radio wave propagation. Because combat and HA/DR operations are highly time-sensitive, the WMN must be designed quickly and with as little guesswork as possible.
A wireless mesh network comprises fixed APs that use separate radio systems to provide two levels of network connectivity (herein the term access point is used generically for any type of wireless mesh transmitter or base station device). The fixed position of APs differentiates WMNs from so-called “ad hoc” networks, where APs can be constantly moving. The first connectivity level of a WMN supports AP-to-AP communication, providing the backhaul radio network that routes traffic from source to destination. The second level supports AP-to-client radio communication. Client devices, such as laptops, PDAs, sensors, or other electronic devices, can be mobile within the WMN client coverage area. While a client device is roaming within a contiguous coverage area, APs may seamlessly “hand off” the client to a more appropriate AP without loss of client network connectivity. WMNs may connect to an outside network or the Internet through a gateway (including via a satellite uplink).
There are three different types of WMN architecture as shown in FIGS. 1-3. FIG. 1 shows an infrastructure mesh WMN 10 that includes a plurality of access points 12 and 14 and a plurality of client devices 16-19. Client devices 16-19 communicate to a single AP 12 or 14 at a time, and hence do not route traffic. FIG. 2 shows a client mesh WMN 22 that has client devices 24-26 with no dedicated APs. Each client device 24-26 serves as both a user terminal and as an AP, routing traffic directly to other client devices. FIG. 3 shows a hybrid mesh WMN 28 that includes both a traditional AP and client devices 30-33 that are capable of serving as APs. This invention is concerned with mesh architectures in which wireless APs alone provide traffic routing services; clients do not perform any routing. Additionally, it is assumed that each AP, once positioned, will remain stationary.
Prior design techniques fail to provide suggested wireless AP locations with any assurance of a good solution. Essentially, engineers typically design WMNs based on experience and trial-and-error using limited support tools.